package org.usmile.algorithms.knapsack;

public class _Complete_Knapsack5 {
    public int solve(int[] weights, int[] values, int capacity) {
        int[] dp = new int[capacity + 1];
        for (int i = 0; i < weights.length; i++) {
            for (int c = weights[i]; c <= capacity; c++) {
                dp[c] = Math.max(dp[c], dp[c - weights[i]] + values[i]);
            }
        }

        return dp[capacity];
    }


    public static void main(String[] args) {
        _Complete_Knapsack5 k = new _Complete_Knapsack5();
        int[] w = {3, 4, 5, 2};
        int[] v = {15, 10, 12, 8};
        System.out.println(k.solve(w, v, 10));
    }
}
